package com.wu.entrynodeofloop;

import java.util.HashSet;

/**
 * 链表中环的入口点
 * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null
 *
 * @author lynn
 * @date 2020/7/29 - 15:08
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        //方案1：
       /* HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode temp = pHead;
        set.add(temp);
        while (temp != null){
            if (!set.contains(temp.next)){
                set.add(temp.next);
            }else {
                return temp.next;
            }
            temp = temp.next;
        }
        return null;*/
        //方案2：
        //定义快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                ListNode cur = pHead;
                while (cur != slow){
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }
        return null;
    }
}